package 数据结构.章节09._146_单链表;

import 数据结构.章节09._145_基于数组实现线性表.MyList;

/**
 * @author 挚爱之夕
 * @date 2021/10/5 - 10 - 05 - 17:01
 * @Description: 数据结构.章节09._146_单链表
 * @Version: 1.0
 */
public class SingleLinkedList<T> implements MyList<T> {
    @Override
    public boolean hasNext() {
        return cur.next != null;
    }

    @Override
    public T next() {
        return (T)cur.next;
    }

    //头节点
    private ListNode<T> head;
    //当前指向节点
    private ListNode<T> cur;
    //单链表长度
    private int size;

    @Override
    public void add(T o) {
        if(head == null){
            head = new ListNode<T>(o);
            cur = head;
        }else {
            cur.next = new ListNode<T>(o);
            cur = cur.next;
        }
        size++;
    }

    @Override
    public void delete(T o) {
        ListNode<T> p = head;
        ListNode<T> pre = null;
        while(p != null){
            if(p.data.equals(o)){
                if(p == head)
                    head = head.next;
                else
                    pre.next = p.next;
                size--;
                break;
            }
            pre = p;
            p = p.next;
        }
    }

    @Override
    public void delete(int index) {
        if(index>=size||index<0)    //什么都不做
            return;
        ListNode<T> p = head;
        ListNode<T> pre = null;
        if(index == 0){ //头结点
            head = head.next;
            return;
        }
        for (int i = 0; i < index; i++) {
            pre = p;
            p = p.next;
        }
        pre.next = p.next;
        size--;
    }

    @Override
    public void modify(int index, T newElement) {
        ListNode<T> p = head;
        for (int i = 0; i < index; i++) {
            p = p.next;
        }
        p.data = newElement;
    }

    @Override
    public boolean contains(T o) {
        int index = find(o);
        return index>=0;
    }

    @Override
    public int find(T o) {
        ListNode<T> p = head;
        int index = 0;
        while(p!=null){
            if(p.data.equals(o))
                return index;
            p = p.next;
            index++;
        }
        return -1;
    }

    @Override
    public T find(int index) {
        ListNode<T> p = head;
        for (int i = 0; i < index; i++) {
            p = p.next;
        }
        return p.data;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        ListNode<T> p = head;
        while(p!=null){
            sb.append(p.data).append(p.next!=null?" -> ":"");
            p = p.next;
        }
        return sb.toString();
    }
}
